Fundamental Drawing Algorithms in Computer Graphics - Chapter 4 - [Part 1]
- الشابتر ده طويل ف اضطريت اقسمه لجزئين , وكمان الدكتور حاطط قوانين من غير امثلة (هو نزل مثالين بس علي المنصه) انا معرفش بصراحه هيجيب مسائل علي الحاجات دي ولا لا بس انا جبت امثلة كراسة العملي وشرحتها احتياطي.
- هتلاقي جداول وكلام كتير وطويل متتخضش الموضوع سهل اوي هو كل مشكلته انه طويل بس لو بصيت علي الامثله هتفهمها لوحدك اصلا.
- هتلاقي اكواد العملي تحت كل الجورزم للي عايز يجرب بس حسب كلام الدكتور هيا مش علينا حفظ.
- طول بالك وقول بسم الله
الشابتر ده هنقسمه لجزئين: الجزء الأول (اللي إحنا فيه) عن Line Drawing Algorithms، والتاني عن Circle Drawing Algorithms.
- الـ
Drawing Algorithmsهي الخوارزميات اللي بتخلي الكمبيوتر يرسم أشكال أساسية على شاشة مبنية من pixels. - هنفهم ليه بنحتاج نحول الوصف الرياضي للشكل لمجموعة pixels، وبعدين هنتعمق في line drawing algorithms زي
Direct Line Equation,DDA, وBresenham— مع أمثلة تطبيقية لكل واحد.
1) Introduction to Drawing Algorithms
- في
Computer Graphics، رسم الأشكال الأساسية زي الخطوط والدواير حاجة اساسية عشان نعرف نرسم اي object. - غالبا الشكل بيتوصف رياضيا بأرقام:
- الخط بيتحدد بنقطة بداية ونقطة نهاية.
- الدائرة بتتحدد بمركز ونصف قطر.
- المشكلة إن الشاشة مش continuous زي الرياضيات، هيا عبارة عن grid من pixels, عشان كده محتاجين نحول الوصف الرياضي ده لـ pixels تتلون على الشاشة.
الـ Drawing Algorithm بيقرر أنهي pixels تتلون عشان الشكل الرياضي يبان أقرب حاجة للشكل الحقيقي على شاشة raster.
2) Geometric Primitives and Mathematical Description
- خدنا الشابتر الي فات الـ
Geometric Primitivesوعرفنا انها الأشكال الأساسية اللي بنبني منها الرسومات, زي:LineCirclePolygonCurve
- كل primitive ليه وصف رياضي:
- الـ
Line: بيتحدد بـ start point و end point. - الـ
Circle: بيتحدد بـ center و radius.
- الـ
- الوصف الرياضي ده بيبقى في
abstract coordinate space، يعني وصف دقيق على مستوى الرياضيات مش على مستوى الـ pixels.
3) Raster Displays and Rasterization
Rasterization is the process of converting continuous mathematical shapes into a set of discrete pixels.
- الشاشات الحديثة بتبقي
Raster-Based، يعني الصورة فيها عبارة عن pixels مترتبة في grid مستطيل (عشان كده الشكل الرياضي مينفعش يتعرض مباشرة على الشاشة). - لازم الاشكال الرياضية دي تتحول لبكسلات.
Pixel-Based Representation
- عشان نفهم الموضوع، تخيل ان عندنا grid وعايزين نرسم vertical line (خط رأسي) من
(2, 9)لـ(2, 16):- ا
x = 2ثابت. - ا
yبيتحرك من9لـ16.
- ا
- في الرياضة الفرق صغير ,بس في الشاشات الحقيقية الموضوع كبير، الـ resolutions ممكن يعدي
1000 × 1000pixels. - عشان كده الالجورزمز لازم تبقى accurate و efficient، خصوصا في real-time rendering.
4) What are Drawing Algorithms?
Drawing algorithms are fundamental techniques used in computer graphics to render shapes, lines, curves, and other geometric primitives on a screen or image.
- الـ
Drawing Algorithmsبتحدد إزاي lines و circles و curves وباقي primitives تتحول لـ pixels. - الهدف إن الشكل النهائي يبقى قريب قدر الإمكان من الشكل الرياضي المقصود.
- بتستخدم في:
- Video games
- Simulations
- Scientific visualization
- Graphic design tools
5) Essential Drawing Algorithms
| Category | Algorithms |
|---|---|
| Line Drawing | DDA, Bresenham's Line Algorithm |
| Circle Drawing | Basic Equation Method, Midpoint Circle Algorithm, Bresenham's Circle Algorithm, Parametric Circle Algorithm |
| Polygon Drawing | Scan-line Fill, Boundary Fill, Flood Fill |
| Curve Drawing | Bézier Curve, Spline Curve |
| Anti-Aliasing | Xiaolin Wu's Line Algorithm, Supersampling |
| Clipping | Cohen-Sutherland, Liang-Barsky, Sutherland-Hodgman |
| Transformation | Translation, Rotation, Scaling, Shearing |
الشابتر بيركز على implementation توضيحي واحد لكل algorithm عشان يشرح الفكرة الأساسية، والتطبيقات والكود موجودين في كراسة العملي.
6) Line Drawing Algorithms
Line drawing algorithms approximate straight line segments on discrete, pixel-based displays.
- زي ما قلنا قبل كده، الشاشة دي عبارة عن Grid من البيكسلات، فعشان ترسم خط مستقيم مايل، مستحيل يجي بالظبط على البيكسلات، عشان كده بنعمل تقريب (Approximation).
- الـ algorithm الأساسية زي الـ Digital Differential Analyzer (DDA) والـ Bresenham's algorithm بترسم الخط بلون واحد، وده بيعمل المشكله الي شوفناها قبل كده الـ aliasing . وبنستخدم الـ Anti-aliasing اللي بتدمج ألوان البيكسلات اللي حوالين الخط عشان تنعم الحواف دي.
7) Direct Use of Line Equation
Concept
- دي أبسط طريقة ممكن تفكر فيها، وهي إننا نستخدم معادلة الخط المستقيم العادية جداً اللي درسناها في الرياضة في ثانوي.
- عشان نرسم خط باستخدام الـ Slope-intercept form، بنمشي على الخطوات دي:
- بنحسب الميل (Slope) اللي هو
والجزء المقطوع من محور الصادات (Intercept) اللي هو . - بنعمل لوب او بنلف على قيم الـ
اللي بين نقطة البداية والنهاية. - لكل قيمة
، بنحسب قيمة الـ اللي بتقابلها من المعادلة:
- بنحسب الميل (Slope) اللي هو
y = mx + c
- في الآخر بنعمل Plot (رسم) للبيكسل بعد ما نعمل التقريب (Rounding) لقيم
Advantages
- سهلة ومباشرة.
- ممكن تتعامل مع :
positive, negative, zero , or undefined slopes.
Application in Computer Graphics:
- معادلة الخط المستقيم بنستخدمها كأساس في خوارزميات تانية زي:
- ا DDA (Digital Differential Analyzer).
- ا Bresenham's Line Algorithm (using an implicit form).
Disadvantages
- بتعتمد على
Floating-Point Arithmetic(عمليات الكسور العشرية دي بطيئة شوية للكمبيوتر وممكن تدخلنا في rounding errors). - أقل كفاءة من algorithms مبنية على integers زي
Bresenham.
Key Observations
- الخط ممكن يتمثل بأكتر من شكل رياضي.
- في الـ Raster graphics، بنختار البيكسلات الأقرب لمسار الخط المثالي.
- لازم نحافظ على الـ Aspect ratio عشان الشكل ميبقاش مشوه.
مثال من كراسة العملي علي Line Equation
عايزين نرسم خط بين النقطتين
(2,2)و(10,6)باستخدام معادلة الخط المستقيم المباشرة.
Step 1: Initial Calculations
-
أول حاجة بنعملها إننا بنحسب الـ Slope (الميل) اللي بنرمزله بـ
m، والـ Y-intercept (الجزء المقطوع من محور الصادات) اللي بنرمزله بـc. -
حساب الميل (
):- هنعوض في القانون ده عشان نجيب الميل:
- هنعوض في القانون ده عشان نجيب الميل:
-
حساب الـ Y-intercept (
):- هنعوض بنقطة البدايه
2,2في المعادلةc = y - mx(تقدر تعوض بأي نقطة عادي ) عشان نجيب c:
- هنعوض بنقطة البدايه
-
المعادلة النهائية للخط:
- كده معانا
c, mهنعوض بقي في القانونy = mx + c - يبقى المعادلة اللي هنعوض فيها لكل بيكسل هي:
- كده معانا
-
تحديد اتجاه اللوب (Condition):
-
بما إن التغير في السينات
أكبر من التغير في الصادات ، يبقى ده Shallow line (خط مائل للأفقي). عشان كده إحنا هنعمل Loop على الـ (هنزود الـ بمقدار 1 في كل خطوة)، ونحسب الـ من المعادلة.
Step 2: Iterative Table
- هنا بقى بنمسك قيم
Xمن أول 2 لحد 10، وفي كل مرة نعوض في المعادلة بتاعتناy = 0.5x + 1عشان نجيب قيمة الـy. - وطبعا عشان دي أرقام عشرية (Floating-point)، لازم نعمل Rounding (نقرب) في الخر عشان نجيب الـ Pixel الصح.
| Step | x (Loop variable) | y (Calculated: 0.5x+1) | Pixel (after rounding) |
|---|---|---|---|
| 0 | 2 | (2, 2) | |
| 1 | 3 | (3, 3) | |
| 2 | 4 | (4, 3) | |
| 3 | 5 | (5, 4) | |
| 4 | 6 | (6, 4) | |
| 5 | 7 | (7, 5) | |
| 6 | 8 | (8, 5) | |
| 7 | 9 | (9, 6) | |
| 8 | 10 | (10, 6) |
Final Pixels:
(2,2), (3,3), (4,3), (5,4), (6,4), (7,5), (8,5), (9,6), (10,6)

8) Digital Differential Analyzer (DDA)
DDA is a line-drawing algorithm that incrementally computes pixel positions using floating-point arithmetic.
Purpose
- ده بقى Algorithm أذكى شوية. الغرض بتاعه إنه يقرب الخط المستقيم من خلال حساب إحداثيات البيكسلات اللي في النص خطوة بخطوة (Step-by-step).
Key Idea
- الفكرة الأساسية إننا بنزود الـ
Xأو الـYبخطوات صغيرة جداً بناءً على ميل الخط، وبنختار الاتجاه الغالب (Dominant direction) عشان نقلل الحسابات. - يعني بنمشي خطوة خطوة بدل ما نحسب المعادلة كلها من الصفر كل مرة.
Steps
- خد نقطتين:
(x0, y0)و(x1, y1). - احسب الفرق:
- حدد عدد الخطوات (ناخد القيمة الأكبر بين الـ
والـ .):
- احسب مقدار الزيادة في كل خطوة:
- ابدأ من
(x0, y0). - في كل خطوة زود
xبـxincوyبـyinc. - ارسم pixel عند الإحداثيات بعد rounding.
Advantages
- سهل ومفهوم.
- أسهل في التنفيذ من algorithms كتير.
- أسرع من direct line equation عشان بيستخدم incremental generation.
- بيقلل التكرار في الحسابات.
Disadvantages
- لسه بيستخدم
Floating-Point Arithmetic. - ممكن يراكم rounding errors.
- ممكن يبقى أقل دقة عند endpoints.
مثال تطبيقي (DDA)
عايزين نرسم خط بين النقطتين
(2,2)و(10,6)باستخدام DDA.
Step 1: Initial Calculations
- أول حاجة بنعملها إننا بنجيب الفرق بين نقطة النهاية ونقطة البداية، عشان نعرف إحنا هنتحرك مسافة قد إيه على محور السينات والصادات,الفرق ده بنسميه Delta X و Delta Y.
Δx = 10 - 2 = 8
Δy = 6 - 2 = 4
- بعد كده بنحسب الـ Steps. بناخد القيمة الأكبر بين الـ
والـ . ليه؟ عشان نضمن إننا بنمشي خطوة خطوة على المحور الأطول، ويبقى الخط بتاعنا متصل ومفيش فيه فراغات.
steps = max(8, 4) = 8
- أخيراً، بنحسب الـ Increment (مقدار الزيادة). دي القيمة اللي هنزودها على الـ
والـ في كل خطوة. بنقسم المسافة الكلية على عدد الخطوات.
x_inc = Δx / steps = 8 / 8 = 1
y_inc = Δy / steps = 4 / 8 = 0.5
- يبقى كده إحنا فهمنا إن في كل خطوة، الـ
هتزيد بمقدار 1 صحيح، بس الـ هتزيد بمقدار 0.5 (يعني نص خطوة).
Step 2: Iterative Table
- هنا بنبدأ التنفيذ. بنبدأ من أول نقطة
(2.0, 2.0)وكل دورة بنزود الـx_incوالـy_inc. - المشكلة اللي بتظهر هنا زي ما إنت شايف، إن الـ
بتطلع بكسور زي 2.5 و 3.5. طبعا الشاشة مفهاش بكسل ونص, البيكسل ده مربع مش بيتقسم. - عشان كده إحنا لازم نعمل خطوة الـ Rounding (التقريب)، عشان نحول الكسور دي لأرقام صحيحة الجهاز يقدر يفهمها (مثلا 2.5 هتتقرب وتبقى 3).
| Step | x (before rounding) | y (before rounding) | Pixel (after rounding) |
|---|---|---|---|
| 0 | 2.0 | 2.0 | (2, 2) |
| 1 | 3.0 | 2.5 | (3, 3) |
| 2 | 4.0 | 3.0 | (4, 3) |
| 3 | 5.0 | 3.5 | (5, 4) |
| 4 | 6.0 | 4.0 | (6, 4) |
| 5 | 7.0 | 4.5 | (7, 5) |
| 6 | 8.0 | 5.0 | (8, 5) |
| 7 | 9.0 | 5.5 | (9, 6) |
| 8 | 10.0 | 6.0 | (10, 6) |
Final Pixels
(2,2), (3,3), (4,3), (5,4), (6,4), (7,5), (8,5), (9,6), (10,6)

9) Bresenham's Line Algorithm
Bresenham's Line Algorithm is an efficient integer-based algorithm for drawing straight lines on raster displays.
Key Idea
- ا
BresenhamبيستخدمDecision Parameterعشان نختار البيكسل اللي عليه الدور من غير أي كسور. - ميزته إنه بيتجنب floating-point calculations.
- عشان كده أسرع وأنسب للهاردوير.
How It Works
- خد نقطتين:
(x0, y0)و(x1, y1). - احسب:
Δx = x1 - x0
Δy = y1 - y0
-
حدد نوع الخط (بنحدد ميل الخط عشان نعرف هنمشي على أي محور):
- لو
|Δy| <= |Δx|يبقى الخطShallow، (يعني ميله خفيف وأقرب للأفقي). - لو
|Δy| > |Δx|يبقى الخطSteep، (يعني ميله حاد وأقرب للرأسي).
- لو
-
استخدم الـdecision parameter الي هو
p:- في shallow line:
p = 2Δy - Δx
- في steep line:
p = 2Δx - Δy
- بنبدأ من أول نقطة
,وفي كل خطوة بنحدث معامل القرار وبنرسم البيكسل اللي بعده.
مثال تطبيقي (Bresenham)
عايزين نرسم نفس الخط بين النقطتين
(2,2)و(10,6)بس المرة دي باستخدام خوارزمية Bresenham.
Step 1: Initial Values
- اول حاجة بنحدد نقط البداية والنهاية، وبنجيب الفرق بينهم.
x0 = 2, y0 = 2
x1 = 10, y1 = 6
- نحسب الـ Delta X والـ Delta Y:
Δx = 10 - 2 = 8
Δy = 6 - 2 = 4
- بما إن
Δx > Δy، يبقى الخط ده ميله خفيف (Shallow line)، وعشان كده إحنا هنعمل Iterate (نلف) على محور السيناتx(يعني الـxهتزيد دايما بـ 1)، والقرار كله هيبقى: هل نزود الـyولا نسيبها زي ما هي؟
Step 2: Decision Parameter
- عشان ناخد القرار ده من غير ما نستخدم أي كسور، بنحسب حاجة اسمها Decision Parameter (معامل القرار) وبنرمزله بـ
p. أول قيمة ليه بنحسبها كده:
p0 = 2Δy - Δx = 2(4) - 8 = 8 - 8 = 0
-
بعد كده في كل خطوة، بنبص على قيمة الـ
pوبناءً عليها بنقرر: -
لو
p ≥ 0: الـyبتزيد بـ 1، وبنحسب الـpالجديدة بالمعادلة دي:
p = p + 2Δy - 2Δx
- لو
p < 0: الـyبتفضل ثابتة زي ما هي، وبنحسب الـpالجديدة بالمعادلة دي:
p = p + 2Δy
Step 3: Iteration Table
- لاحظ إن كل الحسابات هنا جمع وطرح لأرقام صحيحة (Integers)، مفيش أي Rounding ولا كسور خالص
- لاحظ برده اننا بنزود الـ X كل مره بس الـ Y ساعات اه وساعات لا.
| Step | x | y | p (decision) | Pixel |
|---|---|---|---|---|
| 0 | 2 | 2 | 0 | (2, 2) |
| 1 | 3 | 3 | -8 | (3, 3) |
| 2 | 4 | 3 | 0 | (4, 3) |
| 3 | 5 | 4 | -8 | (5, 4) |
| 4 | 6 | 4 | 0 | (6, 4) |
| 5 | 7 | 5 | -8 | (7, 5) |
| 6 | 8 | 5 | 0 | (8, 5) |
| 7 | 9 | 6 | -8 | (9, 6) |
| 8 | 10 | 6 | — | (10, 6) |
Final Pixels
(2,2), (3,3), (4,3), (5,4), (6,4), (7,5), (8,5), (9,6), (10,6)
- بما إن دي نفس النقط اللي طلعت من الـ DDA، فالرسمة هتكون هي هي بالظبط على الشبكة، بس الفكرة كلها إن الطريقة اللي وصلنا بيها للنقط دي أسرع بكتير ومفيهاش وجع دماغ الكسور.

مقارنة سريعة: DDA vs Bresenham
| اااااااااااااااااااااااااااااااااا | DDA | Bresenham |
|---|---|---|
| الحسابات | بيستخدم كسور (Floating-point) | بيستخدم أعداد صحيحة (Integer-based) |
| التقريب (Rounding) | محتاج rounding في كل خطوة | مش محتاج rounding |
| السرعة | أبطأ نسبيا | أسرع |
| الدقة | ممكن يراكم rounding errors | دقيق |
10) ملخص المحاضرة
اتكلمنا في الجزء ده عن Drawing Algorithms - إزاي الكمبيوتر بيعمل Rasterization ويحول الأشكال الرياضية لـ Pixels على الشاشة.
بالنسبة لـ Line Drawing عرفنا 3 طرق:
- ا Direct Line Equation (
y = mx + c) - سهلة وبديهية بس فيها Floating-Point و Rounding Errors - ا DDA - بيحسب Incrementally خطوة بخطوة، أسهل من Direct بس لسه فيه Floating-Point ومحتاج Rounding
- ا Bresenham's Line Algorithm - الأسرع عشان Integer-Based بالكامل وبيستخدم Decision Parameter، مش محتاج Rounding ولا كسور